//
// Description: 17. 电话号码的字母组合
// Created by Loading on 2022/3/27.
//

#include <bits/stdc++.h>

using namespace std;

vector<string> letterCombinations(string digits) {
    vector<string> res;
    int n = digits.size();
    if (!n) {
        return res;
    }
    // 设置映射关系
    unordered_map<char, string> m{{'2', "abc"},
                                  {'3', "def"},
                                  {'4', "ghi"},
                                  {'5', "jkl"},
                                  {'6', "mno"},
                                  {'7', "pqrs"},
                                  {'8', "tuv"},
                                  {'9', "wxyz"}};

    function<void(int, string &)> backtrack = [&](int index, string &s) {
        if (index == n) {
            res.emplace_back(s);
        } else {
            string value = m[digits[index]];
            for (auto c : value) {
                s += c;
                backtrack(index + 1, s);
                s.pop_back();
            }
        }
    };

    string tmp;
    backtrack(0, tmp);

    return res;
}

int main() {
    string digits = "23";
    auto res = letterCombinations(digits);
    for (const auto& s : res) {
        cout << s << endl;
    }

    return 0;
}